{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 二元搜索树 （Binary Search Tree）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 节点类\n",
    "class Node:\n",
    "    # 用类成员函数进行节点初始化\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.lchild = None\n",
    "        self.rchild = None\n",
    "\n",
    "# BST树类\n",
    "class BST:\n",
    "    # 用类成员函数进行BST初始化\n",
    "    def __init__(self, node_list):\n",
    "        self.root = Node(node_list[0])\n",
    "        for value in node_list[1:]:\n",
    "            self.insert(value)\n",
    "    # 搜索拥有某值的节点操作\n",
    "    def search(self, node, parent, value):\n",
    "        if node is None:\n",
    "            return False, node, parent\n",
    "        if node.value == value:\n",
    "            return True, node, parent\n",
    "        # 小的在左孩子，大于等于的在右孩子\n",
    "        if node.value > value:\n",
    "            return self.search(node.lchild, node, value)\n",
    "        else:\n",
    "            return self.search(node.rchild, node, value)\n",
    "\n",
    "    # 插入某值的节点操作\n",
    "    def insert(self, value):\n",
    "        flag, n, p = self.search(self.root, self.root, value)\n",
    "        if not flag:\n",
    "            new_node = Node(value)\n",
    "            if value > p.value:\n",
    "                p.rchild = new_node\n",
    "            else:\n",
    "                p.lchild = new_node\n",
    "\n",
    "    # 删除某值的节点\n",
    "    def delete(self, root, value):\n",
    "        flag, n, p = self.search(root, root, value)\n",
    "        if flag is False:\n",
    "            print(\"Can't find the key! Delete failed!\")\n",
    "        else:\n",
    "            if n.lchild is None:\n",
    "                if n == p.lchild:\n",
    "                    p.lchild = n.rchild\n",
    "                else:\n",
    "                    p.rchild = n.rchild\n",
    "                del p\n",
    "            elif n.rchild is None:\n",
    "                if n == p.lchild:\n",
    "                    p.lchild = n.lchild\n",
    "                else:\n",
    "                    p.rchild = n.lchild\n",
    "                del p\n",
    "            else:\n",
    "                pre = n.rchild\n",
    "                # 当左右孩子都为空时\n",
    "                if pre.lchild is None:\n",
    "                    n.value = pre.value\n",
    "                    n.rchild = pre.rchild\n",
    "                    del pre\n",
    "                else:\n",
    "                    next = pre.lchild\n",
    "                    while next.lchild is not None:\n",
    "                        pre = next\n",
    "                        next = next.lchild\n",
    "                    n.value = next.value\n",
    "                    pre.lchild = next.rchild\n",
    "                    del p\n",
    "\n",
    "    # 先序遍历\n",
    "    def pre_order_traverse(self, node):\n",
    "        if node is not None:\n",
    "            print(node.value)\n",
    "            self.pre_order_traverse(node.lchild)\n",
    "            self.pre_order_traverse(node.rchild)\n",
    "\n",
    "    # 中序遍历\n",
    "    def in_order_traverse(self, node):\n",
    "        if node is not None:\n",
    "            self.in_order_traverse(node.lchild)\n",
    "            print(node.value)\n",
    "            self.in_order_traverse(node.rchild)\n",
    "\n",
    "    # 后序遍历\n",
    "    def post_order_traverse(self, node):\n",
    "        if node is not None:\n",
    "            self.post_order_traverse(node.lchild)\n",
    "            self.post_order_traverse(node.rchild)\n",
    "            print(node.value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "array = [3, 4, 8, 1, 5, 7, 2]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 创建二元搜索树"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "bst = BST(array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "7\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "bst.in_order_traverse(bst.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Can't find the key! Delete failed!\n"
     ]
    }
   ],
   "source": [
    "# 能够降序排序的就是中序遍历\n",
    "bst.delete(bst.root, 9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "bst.delete(bst.root, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "7\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "bst.in_order_traverse(bst.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "bst.insert(6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "6\n",
      "7\n",
      "8\n"
     ]
    }
   ],
   "source": [
    "bst.in_order_traverse(bst.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
